import java.util.Arrays;

public class TestHaeap {
    public int[] elem;
    public int usedSize;

    public TestHaeap() {
        this.elem = new int[10];
    }
    public void initArray(int[] array){
        for (int i = 0; i <array.length ; i++) {
            elem[i]=array[i];
            usedSize++;
        }
    }
    public void creatHeap(){
        for (int parent = usedSize-1-1/2; parent>=0 ; parent--) {
            siftDown(parent,usedSize);
        }
    }

    /***
     * 向下调整的方法
     * @param parent 每颗子树根节点的下标
     * @param usedSize 每颗子树是否调整结束的位置
     */
    private void siftDown(int parent,int usedSize){
        int child=2*parent+1;
        //至少有一个左孩子
        while (child<usedSize){
            if (child+1<usedSize&&elem[child]<elem[child+1]){
                child++;
            }
            //代码走到这里child一定是最大孩子的下标
            if (elem[child]>elem[parent]){
                //交换
                swap(parent,child);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }
    //交换方法
    private void swap(int i,int j){
        int temp=elem[i];
        elem[i]=elem[j];
        elem[j]=temp;
    }
    public void offer(int val){
        if (isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize]=val;
        siftsUp(usedSize);
        usedSize++;

    }
     private void siftsUp(int child){
        int parent=child-1/2;
        while (child>0){
            if (elem[child]>elem[parent]){
                swap(child,parent);
                child=parent;
                parent=child-1/2;
            }else {
                break;
            }
        }
     }
     public boolean isFull(){
        return usedSize==elem.length;
     }
}
